const { log } = require("console");
const { el, fa } = require("element-plus/es/locales.mjs");

// 最大 字母连续长度
function longestContinuousSubstring(val) {
  let arr = val.split("");
  let maxLenght = 0;
  let currentLength = 1;

  for (let i = 1; i < arr.length; i++) {
    if (arr.charCodeAt(i) - arr.charCodeAt(i - 1) == 1) {
      currentLength++;
    } else {
      maxLenght = Math.max(maxLenght, currentLength);
      currentLength = 1;
    }
  }
  return maxLenght;
}
// 两数之和
function twoSum(nums, target) {
  // for (let i = 0; i < nums.length; i++) {
  //    for (let j = i+1; j < nums.length; j++) {
  //       if(nums[i] + nums[j] == target) {
  //          return [i, j];
  //       }
  //    }
  // }
  let map = {};
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (map[complement] !== undefined) {
      return [map[complement], i];
    }
    map[nums[i]] = i;
  }
}
// 罗马数转整数
function romanToInt(s) {
  let sArr = s.split("");
  const map = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  };
  let result = 0;
  for (let i = 0; i < sArr.length; i++) {
    if (map[sArr[i]] < map[sArr[i + 1]]) {
      result += map[sArr[i + 1]] - map[sArr[i]];
      i++;
    } else {
      result += map[sArr[i]];
    }
  }
  return result;
}
// 最长公共前缀
function longestCommonPrefix(strs) {
  if (!strs.length) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (!prefix) return "";
    }
  }
  return prefix;
}
//  找到小镇的法官
function findJudge(n, trust) {
  // replaceAll替换多个不同符号
  // let str = 'A man, a plan, a canal: Panama';
  // 正则去除所有标点符号和特殊符号下划线
  // console.log(str.replaceAll(/[^a-zA-Z0-9]/g, ''));
  // console.log(str.replaceAll(/[\W]/g, ''));

  // 笨方法
  // if (n == 1 && !trust.length) return n;
  // if (!trust.length && n == 2) return -1;
  // // 总人数 n，居民 n-1， 法官 1
  // let people = [];
  // for (let i = 1; i <= n; i++) {
  //    people.push(i);
  // }
  // // 找出所有居民的节点，
  // let nodeArr = new Set();
  // for (let i = 0; i < trust.length; i++) {
  //    nodeArr.add(trust[i][0]);
  // }
  // // 找出疑是法官的节点
  // let result = people.filter((item) => !Array.from(nodeArr).includes(item))[0];
  // let copyTrust = [];
  // // 法官有且只有一个 result, 不存在返回 -1
  // for (let i = 0; i < trust.length; i++) {
  //    for (const str of nodeArr) {
  //       if (trust[i][0] == str && trust[i][1] == result) {
  //          copyTrust.push(trust[i]);
  //       }

  //    }
  // }
  // if(copyTrust.length == n-1) return result;
  // return -1;
  // 优化
  if (n == 1 && !trust.length) return n;
  // 创建信任的数组
  let trustBy = new Array(n + 1).fill(0);
  // 创建被信任的数组
  let trustArr = new Array(n + 1).fill(0);
  // 遍历 trust 数组，更新 trustArr 和 trustBy 数组
  for (const [x, y] of trust) {
    trustBy[x]++;
    trustArr[y]++;
  }
  for (let i = 1; i <= n; i++) {
    if (trustArr[i] == n - 1 && trustBy[i] == 0) return i;
  }
  return -1;
}
// 最佳观光组合
function maxScoreSightseeingPair(values) {
  // 数据量大时运行时间过长
  // let max = 0;
  // // 遍历数组
  // for(let i = 0; i < values.length; i++) {
  //    for (let j = i+1; j < values.length; j++){
  //       if(values[i] + values[j] + i - j > max)
  //          max = values[i] + values[j] + i - j;
  //    }
  // }
  // return max;
  // 优化
  let maxSum = 0; // 最大值
  let maxitem = values[0] + 0; // 当前值 即 i项 + i
  for (let j = 1; j < values.length; j++) {
    maxSum = Math.max(maxSum, maxitem + values[j] - j);
    maxitem = Math.max(maxitem, values[j] + j);
  }
  return maxSum;
}
// 字符串中最多数目的子序列
function maxRepOpt(text, pattern) {
  let sum = 0,
    startnum = 0,
    endnum = 0;
  for (const str of text) {
    // 判断pattern[0]与pattern[1]相同且字符出现在第一位时 避免重复计算第一次
    if (str == pattern[1]) {
      sum += startnum;
      endnum++;
    }
    if (str == pattern[0]) {
      startnum++;
    }
  }
  return sum + Math.max(startnum, endnum);
}
// 公司命名 TODO
function distinctNames(ideas) {
  // 分组，首字母集合，剩余字符串集合
  let initial = [];
  let result = [];
  for (let i = 0; i < ideas.length; i++) {
    initial.push(ideas[i][0]);
    result.push(ideas[i].slice(1));
  }
  // 并集与差集
  let unicon = new Set();
  for (let i = 0; i < initial.length; i++) {
    for (let j = result.length - 1; j >= 0; j--) {
      if (ideas[i] != initial[i] + result[j])
        unicon.add(ideas[i] + " " + ideas[j]);
    }
  }
  console.log(unicon);

  return unicon.size;
}
// 公交站间的距离
function distanceBetweenBusStops(distance, start, destination) {
  let positive = 0;
  let negative = 0;
  let len = distance.length;
  for (let i = 0; i < len; i++) {
    if (start < destination) {
      // 顺时针取值
      if (i >= start && i < destination) {
        positive += distance[i];
      } else {
        negative += distance[i];
      }
    } else {
      // 逆时针取值
      if (i >= destination && i < start) {
        negative += distance[i];
      } else {
        positive += distance[i];
      }
    }
  }
  return Math.min(positive, negative);
}
// 字符串中的第一个唯一字符
function firstUniqChar(s) {
  let map = new Map();
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      map.set(s[i], map.get(s[i]) + 1);
    } else {
      map.set(s[i], 1);
    }
  }
  for (let [key, value] of map) {
    if (value == 1) {
      return s.indexOf(key);
    }
  }
  return -1;
}
function intersect(nums1, nums2) {
  let map = new Map();
  let map2 = new Map();
  for (let i = 0; i < nums1.length; i++) {
    if (map.has(nums1[i])) {
      map.set(nums1[i], map.get(nums1[i]) + 1);
    } else {
      map.set(nums1[i], 1);
    }
  }
  for (let i = 0; i < nums2.length; i++) {
    if (map2.has(nums2[i])) {
      map2.set(nums2[i], map2.get(nums2[i]) + 1);
    } else {
      map2.set(nums2[i], 1);
    }
  }
  console.log(map, map2);

  let result = [];
  for (let [key, value] of map2) {
    if (map.has(key)) {
      for (let i = 0; i < Math.min(map.get(key), value); i++) {
        result.push(key);
      }
    }
  }
  return result;
}

function isValid(s) {
  if (s.length % 2 == 1) return false;
  let map = s.split("");
  let sum = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] == "(" || "{" || "[") {
      for (let j = map.length - 1; j < map.length; j--) {
        if (
          s[i] + map[j] == "()" ||
          s[i] + map[j] == "{}" ||
          s[i] + map[j] == "[]"
        ) {
          map.splice(j, 1);
          sum++;
        }
      }
    }
  }
  return sum == s.length / 2;
}
// 有效的括号
function isValid(s) {
  if (s.length % 2 != 0) return false;
  let map = [];
  for (let str of s) {
    if (str === "(" || str === "{" || str === "[") {
      map.push(str);
    } else {
      if (!map.length) return false;
      if (str === ")" && map.pop() !== "(") return false;
      if (str === "}" && map.pop() !== "{") return false;
      if (str === "]" && map.pop() !== "[") return false;
    }
  }
  return !map.length;
}
//  3 的幂
function isPowerOfThree(n) {
  if (n <= 0) return false;
  for (let i = 0; i < n; i++) {
    if (Math.pow(3, i) == n) return true;
    if (Math.pow(3, i) > n) return false;
  }
}
// 丢失的数字
function missingNumber(nums) {
  let setnums = new Set(nums);
  for (let i = 0; i <= nums.length; i++) {
    if (!setnums.has(i)) return i;
  }
}
// 有效的字母异位词
function isAnagram(s, t) {
  if (s.length != t.length || (s.length == 0 && t.length == 0)) return false;
  let smap = new Map();
  let tmap = new Map();
  for (let i = 0; i < s.length; i++) {
    if (smap.has(s[i])) smap.set(s[i], smap.get(s[i]) + 1);
    else smap.set(s[i], 1);
  }
  for (let i = 0; i < t.length; i++) {
    if (tmap.has(t[i])) tmap.set(t[i], tmap.get(t[i]) + 1);
    else tmap.set(t[i], 1);
  }
  for (const str of s) {
    console.log(smap, tmap, smap.values(str));

    if (smap.get(str) != tmap.get(str)) return false;
  }
  return true;
}
// 回文链表
function isPalindrome(head) {
  const arr = [];
  while (head != null) {
    arr.push(head.val);
    head = head.next;
  }
  let len = arr.length;
  let count = len - 1;
  if (len === 1) return true;
  for (let i = 0; i < len / 2; i++) {
    if (arr[i] != arr[count]) return false;
    count--;
  }
  return true;
}
// 存在重复元素
function containsDuplicate(nums) {
  let numMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    numMap.set(nums[i], numMap.get(nums[i]) + 1 || 1);
    if (numMap.get(nums[i]) > 1) return true;
  }
  return false;
}
// 反转链表
function reverseList(head) {
  let pre = null;
  let cur = head;
  while (cur) {
    let next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
    console.log(cur);
  }
  return pre;
}
// 快乐数
function isHappy(n) {
  let nsum = new Map();
  while (n != 1) {
    let sum = 0;
    n = n + "";
    for (const str of n) {
      sum += Math.pow(str, 2);
    }
    if (sum == 1) return true;
    nsum.set(sum, nsum.get(sum) + 1 || 1);
    if (nsum.get(sum) > 1) return false;
    n = sum;
  }
  return true;
}
//  位1的个数
function hammingWeight(n) {
  // 二进制数
  let binary = n.toString(2);
  let count = 0;
  for (const str of binary) {
    if (str == "1") count++;
  }
  return count;
}
// 颠倒二进制位
function reverseBits(n) {
  let str_n = n.toString(2).split("").reverse();
  for (let i = 0; i < 32; i++) {
    if (str_n[i] == undefined) str_n[i] = 0;
  }
  return parseInt(str_n.join(""), 2);
}
// Excel 表列序号
function titleToNumber(s) {
  let sum = 0;
  for (let i = 0; i < s.length; i++) {
    sum += (s[i].charCodeAt() - 64) * Math.pow(26, s.length - 1 - i);
  }
  return sum;
}
// 多数元素
function majorityElement(nums) {
  let numsMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    numsMap.set(nums[i], numsMap.get(nums[i]) + 1 || 1);
    if (numsMap.get(nums[i]) > nums.length / 2) return nums[i];
  }
}
// 合并两个有序链表
function mergeTwoLists(list1, list2) {
  let arr = new ListNode(-1);
  let cur = arr;
  while (list1 != null && list2 != null) {
    if (list1.val <= list2.val) {
      cur.next = list1;
      list1 = list1.next;
    } else {
      cur.next = list2;
      list2 = list2.next;
    }
    cur = cur.next;
  }
  cur.next = list1 === null ? list1 : list2;
  return arr.next;
}
// 删除有序数组中的重复项
function removeDuplicates(nums) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === nums[i + 1]) {
      nums.splice(i, 1);
      i--;
    }
  }
  //  性能更好
  let count = 0;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] != nums[count]) {
      count++;
      nums[count] = nums[i];
    }
  }
  return count + 1;
}
// 找出字符串中第一个匹配项的下标
function strStr(haystack, needle) {
  let index = -1;
  let len = haystack.length;
  for (let i = 0; i < len; i++) {
    console.log(haystack.slice(i, needle.length));

    if (
      haystack[i] === needle[0] &&
      haystack.split(i, i + needle.length) == needle
    ) {
      index = i;
      return;
    }
  }
  return index;
}
// 加一
function plusOne(digits) {
  let len = digits.length;
  digits[len - 1] += 1;
  for (let i = len - 1; i >= 0; i--) {
    if (digits[i] == 10) {
      digits[i] = 0;
      if (i == 0) digits.unshift(1);
      else digits[i - 1] += 1;
    }
  }
  return digits;
}
// x 的平方根
function mySqrt(x) {
  let i = 0;
  while (i >= 0 && i * i <= x) {
    i++;
  }
  return i;
}
// 爬楼梯
function climbStairs(n) {}

// 合并两个有序数组
function merge(nums1, m, nums2, n) {
  if ((m == 0 && n == 0) || (m != 0 && n == 0)) {
    console.log("111");
    return nums1;
  }
  let j = n - 1;
  for (let k = m; k < m + n; k++) {
    console.log("3333");
    nums1[k] = nums2[j];
    j--;
  }
  return nums1.sort((a, b) => a - b);
}
// 二叉树的中序遍历: 指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次， 而且仅被访问一次,中序遍历：按照 左-根-右 的次序遍历
function inorderTraversal(root) {
  let arr = [];
  function dfs(node) {
    if (node) {
      dfs(node.left);
      arr.push(node.val);
      dfs(node.sqrt);
    }
  }
  dfs(root);
  return arr;
}
// 对称二叉树
function isSymmetric(root) {}
// 杨辉三角
function generate(numRows) {
  let arr = [];
  for (let i = 0; i < numRows; i++) {
    let row = [];
    for (let j = 0; j <= i; j++) {
      if (j == 0 || j == i) {
        row.push(1);
      } else {
        row.push(arr[i - 1][j - 1] + arr[i - 1][j]);
      }
    }
    arr.push(row);
  }
  return arr;
}

// 买卖股票的最佳时机
function maxProfit(prices) {
  let min = prices[0];
  let max = 0;
  for (let i = 0; i < prices.length; i++) {
    if (min > prices[i]) {
      min = prices[i];
    } else {
      max = Math.max(max, prices[i] - min);
    }
  }
  return max;
}
// 移除所有非字母数字字符
function replaceAll(str) {
  return str.replace(/[^a-zA-Z0-9]/g, "");
}
// 验证回文串
function isPalindrome(s) {
  // 大写字母转小写
  s = s.toLowerCase().replace(/[^a-zA-Z0-9]/g, "");
  if (s.length == 0) return true;
  for (let i = 0; i < s.length / 2; i++) {
    if (s.length % 2 === 0) {
      if (s[i] !== s[s.length - 1 - i]) {
        return false;
      }
    } else {
      if (i < (s.length - 1) / 2 && s[i] !== s[s.length - 1 - i]) {
        return false;
      }
    }
  }
  return true;
  let len = s.length;
  let j = parseInt(s.length / 2);
  for (let i = 0; i < j; i++) {
    if (s[i] != s[len - 1]) {
      return false;
    } else {
      len--;
    }
  }
  return true;
}
// 只出现一次的数字
function singleNumber(nums) {
  const nummap = new Map();
  for (let i = 0; i < nums.length; i++) {
    nummap.set(nums[i], nummap.has(nums[i]) ? nummap.get(nums[i]) + 1 : 1);
  }
  for (let [key, value] of nummap) {
    if (value === 1) {
      return key;
    }
  }
}
// 平方数之和
function judgeSquareSum(c) {
  let left = 0;
  let sqrt = parseInt(Math.sqrt(c));
  while (left <= sqrt) {
    let sum = left * left + sqrt * sqrt;
    if (sum === c) {
      return true;
    } else if (sum < c) {
      left++;
    } else {
      sqrt--;
    }
  }

  return false;
}
//
var losingPlayer = function (x, y) {
  let count = 0;
  if (x == y / 4) {
    count = x;
  } else {
    count = parseInt(Math.min(x, y / 4));
  }
  return count % 2 == 0 ? "Bob" : "Alice";
};
// 长度为 K 的子数组的能量值 I
function resultsArray(nums, k) {
  let results = [];
  let n = nums.length;
  for (let i = 0; i < n - k + 1; i++) {
    if (
      nums[i + k - 1] - nums[i] == k - 1 &&
      nums[i + k - 1] - nums[i + k - 2] == 1 &&
      k > 1
    ) {
      let isTrue = true;
      for (let j = i; j < k + i; j++) {
        if (nums[j] - nums[i] !== j - i) {
          isTrue = false;
          break;
        }
      }
      results.push(isTrue ? nums[i + k - 1] : -1);
    } else if (nums[i + k - 1] - nums[i] == k - 1 && k == 1) {
      results.push(nums[i]);
    } else {
      results.push(-1);
    }
  }
  return results;
}
// 长度为 K 的子数组的能量值 II
function resultsArray(nums, k) {
  let n = nums.length;
  let results = new Array(n - k + 1).fill(-1);
  let count = 0;
  for (let i = 0; i < n; i++) {
    count = i === 0 || nums[i] - nums[i - 1] !== 1 ? 1 : count + 1;
    if (count >= k) results[i - k + 1] = nums[i];
  }

  return results;
}
// 回文数
function isPalindrome(x) {
  let str = x.toString();
  if (str.length == 1) return true;
  for (let i = 0; i < str.length / 2; i++) {
    if (str[i] !== str[str.length - 1 - i]) {
      return false;
    }
  }
  return true;
}
// 移除元素
function removeElement(nums, val) {
  let len = nums.length;
  let count = 0;
  for (let i = 0; i < len; i++) {
    if (nums[i] !== val) {
      nums[count] = nums[i];
      count++;
    }
  }
  return count;
}
// 搜索插入位置
function searchInsert(nums, target) {
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    if (nums[i] === target) {
      return i;
    }
    if (nums[i] > target) {
      return i - 1;
    }
  }
  return len;
}
// 找到所有数组中消失的数字
function findDisappearedNumbers(nums) {
  const len = nums.length;
  let arr = [];
  for (const val of nums) {
    const i = (val - 1) % len;
    nums[i] += len;
  }
  for (let i = 0; i < len; i++) {
    if (nums[i] <= len) {
      arr.push(i + 1);
    }
  }
  return arr;
}
// 相同的树
function isSameTree(p, q) {
  return JSON.stringify(p) === JSON.stringify(q);
  let cardMap = new Map();
  cardMap.set(1, 1);
}
// 统计满足 K 约束的子字符串数量 I

function countKDifference(s, k) {
  let count = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j < s.length; j++) {
      if (Math.abs(s[i] - s[j]) == k) {
        count++;
      }
    }
  }
  return count;
}
// 赎金信
function canConstruct(ransomNote, magazine) {
  let mapnote = new Map();
  for (const str of ransomNote) {
    mapnote.set(str, mapnote.has(str) ? mapnote.get(str) + 1 : 1);
  }
  for (const str of magazine) {
    if (mapnote.has(str)) {
      mapnote.set(str, mapnote.get(str) - 1);
    }
  }
  for (const val of mapnote.values()) {
    if (val > 0) {
      return false;
    }
  }
  return true;
}
// 罗马数字转整数
var romanToInt = function (s) {
  let obj = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
  let sum = 0;
  for (let i = 0; i < s.length; i++) {
    if (obj[s[i]] < obj[s[i + 1]]) {
      sum += obj[s[i + 1]] - obj[s[i]];
      i = i + 1;
    } else {
      sum += obj[s[i]];
    }
  }
  return sum;
};
// 最后一个单词的长度
function lengthOfLastWord(s) {
  let len = s.length;
  let count = 0;
  for (let i = len - 1; i >= 0; i--) {
    if (s[i] !== " ") {
      count++;
    } else {
      if (count > 0) {
        return count;
      }
    }
  }
  return count;
  let arr = s.split(" ");
  let result = "";
  for (let i = 0; i < arr.length; i++) {
    if (arr[i].length) {
      result = arr[i];
    }
  }
  return result.length;
}
// 判断子序列
function isSubsequence(s, t) {
  let count = 0;
  for (let i = 0; i < t.length; i++) {
    if (s[count] === t[i]) {
      count++;
    }
  }
  return count === s.length;
  let idx = s.length - 1;
  for (let i = t.length - 1; i >= 0; i--) {
    if (t[i] == s[idx]) {
      idx--;
    }
  }
  return idx == -1 ? true : false;
}
// 同构字符串
function isIsomorphic(s, t) {
  let sobj = {};
  let tobj = {};
  // 在原字符串删除字符串中某个字符，返回删除后的字符串
  // 'ssssss' 删除一个s 再返回剩余字符串splice
  function delStr(str, index) {
    return str.slice(0, index) + str.slice(index + 1);
  }

  for (let i = 0; i < s.length; i++) {
    const x = s[i],
      y = t[i];
    if ((sobj[x] && sobj[x] !== y) || (tobj[y] && tobj[y] !== x)) {
      return false;
    }
    sobj[x] = y;
    tobj[y] = x;
  }
  return true;
}
// 有效的字母异位词
function isAnagram(s, t) {
  return s.split("").sort().join("") === t.split("").sort().join("");
}
// 存在重复元素 II
function containsNearbyDuplicate(nums, k) {
  let result = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (result.has(nums[i]) && i - result.get(nums[i]) <= k) {
      return true;
    }
  }
  return false;
}
// 汇总区间
function summaryRanges(nums) {
  let result = [];
  let start = 0;
  let end = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i + 1] - nums[i] == 1) {
      end++;
    } else {
      if (start == end) {
        result.push(nums[i].toString());
      } else {
        result.push(nums[start] + "->" + nums[end]);
      }
      start = i + 1;
      end = i + 1;
    }
  }
}
// 二进制求和
function addBinary(a, b) {
  let sum = 0;
  let i = a.length - 1;
  let j = b.length - 1;
  let obj = {
    0: 0,
    1: 1,
    "00": 0,
    "01": 1,
    10: 1,
    11: 0,
  };
  while (i >= 0 || j >= 0) {
    sum = obj[sum];
    if (i >= 0) {
      sum = obj[sum + a[i]];
      i--;
    }
    if (j >= 0) {
      sum = obj[sum + b[j]];
      j--;
    }
  }
  return sum;
}
